package day03;
//双边快排：设左一为基准点，取两个指向左一和右一的指针left和right,从右边开始（也可以从左边），如果right大于或等于基准点，则right左移
//即right--，如果right小于基准点，则用left和基准点比较，如果小于等于基准点，则left右移，即left++，如果大于基准点，则left和right的
//值交换位置且right--,然后继续从right进行上述比较变换，当left等于right时，将基准点的值和重合的值交换，此时完成第一次分割，通过对起始
//值的设置进行递归调用，即可实现双边快排

import java.util.Arrays;

public class HW_1_DoubleQuick {
    public static void main(String[] args) {
        int[] arr = new int[]{4,7,6,5,3,2,8,1};
        exChange(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void exChange(int[] arr,int start,int end) {
        if (start >= end) {return;}
        int p=start;
        int left=start;
        int right=end;
        while(left!=right) {
            while(arr[right]>arr[p]&&right>left){
                right--;
            }
            while(arr[left]<=arr[p]&&left<right){
                left++;
            }

        if (right > left) {
            int temp = 0;
            temp = arr[right];
            arr[right] = arr[left];
            arr[left] = temp;
            //交换元素之后，右指针向左移动一位，从新的元素开始比较
            right--;
        }
        //两个指针重合，就和基准元素进行交换位置
        if (right == left) {
            int temp = 0;
            temp = arr[left];
            arr[left] = arr[p];
            arr[p] = temp;
        }}
        p=left;
        exChange(arr,start,p-1);
        exChange(arr,p+1,end);
    }
}
